/**
 * @ClassName UF
 * @Description 加权quick-union算法
 * @Author Fanxc
 * @DATE 2021/1/22 19:35
 * @Version 1.0
 */
public class WeightedQuickUnionUF {
    private int[] id;
    private int[] sz;
    private int count;

    public WeightedQuickUnionUF(int N){
        count=N;
        id=new int[N];
        for (int i = 0; i < N; i++) {
            id[i]=i;
        }
        sz=new int[N];
        for (int i = 0; i < N; i++) {
            sz[i]=i;
        }
    }
    public int count(){
        return count;
    }


    public boolean connected(int p,int q){
        return find(p)==find(q);
    }


    //quick-union算法
    private int find(int p){
        while (p!=id[p]){
            p=id[p];
        }
        return p;
    }

    public void union2(int p,int q){
        int i=find(p);
        int j=find(q);
        if (i==j){
            return;
        }
        //将小数的根节点连接到大树的根节点
        if (sz[i]<sz[j]){
            id[i]=j;
            sz[j]+=sz[i];
        }else {
            id[j]=i;
            sz[i]+=sz[j];
        }
        count--;
    }

}
